“Evaluation and optimization of innovative production systems of goods and services” HEURISTIC METHODS FOR PROBLEMS WITH BLOCKING CONSTRAINTS SOLVING JOBSHOP SCHEDULING

ABSTRACT: Jobshop problem is one of the most difficult classical scheduling problems. Very simple special cases of jobshop problem are strongly NP-hard. This paper deals with makespan minimization in jobshop scheduling problems with a specific blocking constraint met in several industrial problems. We also propose and define another new type of blocking constraint. After a problem description and the definitions of different blocking constraints, possible conflicts situations are considered. A heuristic method is then proposed which avoids conflicting situations and numerical results with specific blocking constraints are presented and discussed